//零钱兑换二  力扣518
//完全背包（每个物品可无限次选取）  放满背包有几种方法（放第i种物品的方法数+不放第i种物品的方法数）
//组合   先遍历物品，再遍历背包
//二维写法
class Solution {
public:
	int change(int amount, vector<int>& coins) {
		vector<vector<uint64_t>> dp(coins.size(),vector<uint64_t>(amount+1));
		//初始化
		for(int i = 0; i <= amount; i++)
			if(i % coins[0] == 0) dp[0][i] = 1;
		for(int i = 0; i < coins.size(); i++)
			dp[i][0] = 1;
		//递推
		for(int i = 1; i < coins.size(); i++)
		{
			for(int j = 1; j <= amount; j++)
			{
				if(j < coins[i]) dp[i][j] = dp[i-1][j];
				else dp[i][j] = dp[i][j-coins[i]] + dp[i-1][j];
			}
		}
		return dp[coins.size()-1][amount]; 
		
	}
};
